package q23

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func mergeKLists(lists []*ListNode) *ListNode {
	var head *ListNode
	var curNode *ListNode
	var columnMin int //最小值
	var columnMinB bool = false

	for {
		columnMinB = false
		empty := true
		minIndex := []int{}

		//轮训找出当前最小的
		for i, node := range lists {
			if node == nil {
				continue
			}

			if !columnMinB {
				columnMin = node.Val
				columnMinB = true
			}

			empty = false
			val := node.Val
			if val == columnMin {
				minIndex = append(minIndex, i)
			} else if val < columnMin {
				minIndex = []int{i}
				columnMin = val
			}
		}

		if empty {
			break
		}

		for _, index := range minIndex {
			lists[index] = lists[index].Next
			if curNode == nil {
				head = &ListNode{Val: columnMin}
				curNode = head
			} else {
				nodeTmp := &ListNode{Val: columnMin}
				curNode.Next = nodeTmp
				curNode = nodeTmp
			}
		}

	}

	return head
}
